import java.util.Random;
//快排
public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        int i=0,j=nums.length-1;
        int temp = nums[0];
        fastSort(nums,i,j,k);
        return  nums[k-1];

    }
    public void fastSort(int[] nums,int i,int j,int k){
        if(i >= j){
            return ;
        }
        Random r = new Random();
        int p = r.nextInt(j-i+1)+i;
        swap(nums,i,p);
        int begin = i,end = j;
        int temp = nums[i];
        while(i<j){
            while(nums[j] <= temp && i<j)j--;
            nums[i] = nums[j];
            while(nums[i] > temp && i<j)i++;
            nums[j] = nums[i];
        }
        nums[i] = temp;
        if(k-1 == i){
            return;
        }
        else if(i > k-1)
            fastSort(nums,begin,i-1,k);
        else
            fastSort(nums,i+1,end,k);
    }
    public void swap(int[] nums,int i,int j){
        int t;
        t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

//堆排
class Solution {
    public int findKthLargest(int[] nums, int k) {
        create_heap(nums,nums.length/2-1,nums.length);
        heapSort(nums,k);
        return nums[nums.length-k];
    }
    public void create_heap(int[] nums,int n,int limit){
        for(int i = n;i>=0;i--){
            createHeap(nums,i,limit);
        }
    }
    public void createHeap(int[] nums, int n,int limit){
        if(n > limit/2-1){
            return;
        }
        int leftChild = 2*n+1,rightChild = 2*n+2;
        int max = n;
        if(leftChild < limit && nums[leftChild] > nums[max])
            max = leftChild;
        if(rightChild < limit && nums[rightChild] > nums[max])
            max = rightChild;
        if(max != n){
            swap(nums,max,n);
            createHeap(nums,max,limit);
        }

    }
    public void heapSort(int[] nums,int k){
        for(int j = nums.length-1;j>=nums.length-k;j--){
            swap(nums,0,j);
            create_heap(nums,0,j-1);
        }
    }
    public void swap(int[] nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}